|
The binary GCD algorithm, also known as Stein's algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm; it replaces division with arithmetic shifts, comparisons, and subtraction. Although the algorithm was first published by the Israeli physicist and programmer Josef Stein in 1967, it may have been known in 1st-century China. ==Algorithm== The algorithm reduces the problem of finding the GCD by repeatedly applying these identities: # gcd(0, ''v'') = ''v'', because everything divides zero, and ''v'' is the largest number that divides ''v''. Similarly, gcd(''u'', 0) = ''u''. gcd(0, 0) is not typically defined, but it is convenient to set gcd(0, 0) = 0. # If ''u'' and ''v'' are both even, then gcd(''u'', ''v'') = 2·gcd(''u''/2, ''v''/2), because 2 is a common divisor. # If ''u'' is even and ''v'' is odd, then gcd(''u'', ''v'') = gcd(''u''/2, ''v''), because 2 is not a common divisor. Similarly, if ''u'' is odd and ''v'' is even, then gcd(''u'', ''v'') = gcd(''u'', ''v''/2). # If ''u'' and ''v'' are both odd, and ''u'' ≥ ''v'', then gcd(''u'', ''v'') = gcd((''u'' − ''v'')/2, ''v''). If both are odd and ''u'' < ''v'', then gcd(''u'', ''v'') = gcd((''v'' − ''u'')/2, ''u''). These are combinations of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of step 3 above. The division by 2 results in an integer because the difference of two odd numbers is even.〔In fact, the algorithm might be improved by the observation that if both ''u'' and ''v'' are odd, then exactly one of ''u'' + ''v'' or ''u''−''v'' must be divisible by four. Specifically, assuming ''u'' ≥ ''v'', if ((''u'' xor ''v'') and 2) = 2, then gcd(''u'', ''v'') = gcd((''u'' + ''v'')/4, ''v''), and otherwise gcd(''u'', ''v'') = gcd((''u'' − ''v'')/4, ''v'').〕 # Repeat steps 2–4 until ''u'' = ''v'', or (one more step) until ''u'' = 0. In either case, the GCD is 2''k''''v'', where ''k'' is the number of common factors of 2 found in step 2. The algorithm requires O(n2)〔http://gmplib.org/manual/Binary-GCD.html〕 worst-case time, where n is the number of bits in the larger of the two numbers. Although each step reduces at least one of the operands by at least a factor of 2, the subtract and shift operations take linear time for very large integers (although they're still quite fast in practice, requiring about one operation per word of the representation). An extended binary GCD, analogous to the extended Euclidean algorithm, is given by Knuth along with pointers to other versions.〔, answer to exercise 39 of section 4.5.2〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Binary GCD algorithm」の詳細全文を読む スポンサード リンク
|